home *** CD-ROM | disk | FTP | other *** search
/ Speccy ClassiX 1998 / Speccy ClassiX 98.iso / amiga_system / the_aminet / dev / gcc / ixemulsrc.lha / ixemul-41.4 / library / buddy-alloc.c < prev    next >
C/C++ Source or Header  |  1995-05-27  |  10KB  |  373 lines
  1. /*
  2.  *  This file is part of ixemul.library for the Amiga.
  3.  *  Copyright (C) 1991, 1992  Markus M. Wild
  4.  *
  5.  *  This library is free software; you can redistribute it and/or
  6.  *  modify it under the terms of the GNU Library General Public
  7.  *  License as published by the Free Software Foundation; either
  8.  *  version 2 of the License, or (at your option) any later version.
  9.  *
  10.  *  This library is distributed in the hope that it will be useful,
  11.  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  12.  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13.  *  Library General Public License for more details.
  14.  *
  15.  *  You should have received a copy of the GNU Library General Public
  16.  *  License along with this library; if not, write to the Free
  17.  *  Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18.  *
  19.  *  $Id: buddy-alloc.c,v 1.4 1994/06/19 15:02:51 rluebbert Exp $
  20.  *
  21.  *  $Log: buddy-alloc.c,v $
  22.  *  Revision 1.4  1994/06/19  15:02:51  rluebbert
  23.  *  *** empty log message ***
  24.  *
  25.  *  Revision 1.2  1992/09/14  01:40:24  mwild
  26.  *  change from using aligned blocks (obtained thru an AllocMem/FreeMem/AllocAbs
  27.  *  hack) to using non-aligned blocks. The price for this is an additional
  28.  *  field in every allocated block.
  29.  *
  30.  *  In the same run, change Forbid/Permit into Semaphore locking.
  31.  *
  32.  *  Revision 1.1  1992/05/22  01:42:33  mwild
  33.  *  Initial revision
  34.  *
  35.  */
  36. #define KERNEL
  37. #include "ixemul.h"
  38. #include "kprintf.h"
  39. #include <exec/memory.h>
  40. #include <stddef.h>
  41.  
  42. /* #define TEST_EXEC_BLOCKS */
  43. /* #define CLOBBER_CHECK */
  44. /* if you enable CLOBBER_CHECK, make sure to adjust MINLOG2 accordingly!! */
  45.  
  46. #ifdef TEST
  47. #ifndef PRETTY_STABLE
  48. #define AllocMem(size,attr)    test_allocmem(size,attr)
  49. #define AllocAbs(size,buf)    test_allocabs(size,buf)
  50. #define FreeMem(buf,size)    test_freemem(buf,size)
  51. #define Forbid()
  52. #define Permit()
  53. #define ix_panic(str) puts(str)
  54. #define P(arg) printf arg
  55. #else
  56. #define P(arg)
  57. #define ix_panic(arg)
  58. #endif
  59. #else
  60. #ifdef DEBUG_VERSION
  61. #define P(arg) KPRINTF (arg)
  62. #define DP(arg) KPRINTF (arg)
  63. #else
  64. #define P(arg)
  65. #define DP(arg)
  66. #endif
  67. #endif
  68.  
  69.  
  70. /* this provides a straight replacement for AllocMem() and FreeMem().
  71.    Being this, it does *not* remember the size of allocation, the
  72.    clients have to do this instead. */
  73.  
  74. /* NOTE: currently only two pools are supported, MEMF_PUBLIC and
  75.          ! MEMF_PUBLIC. No MEMF_CHIP pools are needed by the library
  76.          and are thus not supported */
  77.  
  78.  
  79. /* TUNING: The two parameters that can be adjusted to fine tune
  80.            allocation strategy are MAXSIZE and BUDDY_LIMIT. By setting
  81.            MAXSIZE larger than BUDDY_LIMIT results in less Exec
  82.            overhead, since blocks stay longer in the buddy system.
  83.            Setting MAXSIZE==BUDDY_LIMIT sets memory usage to the
  84.            minimum, at the cost of more Exec calls. */
  85.  
  86.  
  87. /* no request for memory can be lower than this */
  88. #define MINLOG2        4
  89. #define MINSIZE        (1 << MINLOG2)
  90.  
  91. /* this is the size the buddy system gets memory pieces from Exec */
  92. #ifdef TEST_EXEC_BLOCKS
  93. #define MAXLOG2        20    /* get (one) 1M chunk */
  94. #define MAXSIZE        (1 << MAXLOG2)
  95. void *exec_block_address[2] = { 0 };
  96. #else
  97. #define MAXLOG2        15    /* get 32K chunks */
  98. #define MAXSIZE        (1 << MAXLOG2)
  99. #endif
  100.  
  101. /* this is the limit for b_alloc to go straight to Exec */
  102. #define BUDDY_LIMIT    (1 << (MAXLOG2 - 5))    /* but serve only upto 1K */
  103.  
  104. #define PRIVATE_POOL    0
  105. #define PUBLIC_POOL    1
  106. #define NUMPOOLS    2    /* public and !public */
  107. /* attention: don't go larger than 3 pools, or you'll have to change the
  108.               encoding in free_block (only 2 bits for now) */
  109.  
  110. struct free_list {
  111.   u_int  exec_attr;
  112.   struct SignalSemaphore sem;
  113.   struct MinList buckets[MAXLOG2 - MINLOG2];
  114. } free_list[NUMPOOLS] = { { 0, }, { MEMF_PUBLIC, } };
  115.  
  116.  
  117. struct free_block {
  118.   /* to make the smallest allocatable block 16, and not 32 byte, stuff both
  119.      the freelist information and the exec-block address into one long. */
  120.   u_int    pool:2,        /* 0: block is free, > 0: POOL + 1 */
  121.       exec_block:30;    /* shift left twice to get the real address */
  122.  
  123. #ifdef CLOBBER_CHECK
  124.   u_int  magic[5];
  125. #endif
  126.  
  127.   /* from here on, fields only exist while the block is on the free list.
  128.      The application sees a block as a chunk of memory starting at &next */
  129.   struct free_block *next, *prev;    /* min-node compatible */
  130.   int index;
  131. };
  132.  
  133.  
  134. void
  135. init_buddy (void)
  136. {
  137.   int i, l; 
  138.  
  139.   /* don't want such a nightmare of bug-hunt any more... */
  140.   if (sizeof (struct free_block) > MINSIZE)
  141.     {
  142.       ix_panic ("buddy-system: MINSIZE/MINLOG2 too small, increase!");
  143.       Wait (0);
  144.     }
  145.  
  146.   for (l = 0; l < NUMPOOLS; l++)
  147.     {
  148.       for (i = 0; i < MAXLOG2 - MINLOG2; i++)
  149.     NewList ((struct List *) &free_list[l].buckets[i]);
  150.       InitSemaphore (&free_list[l].sem);
  151.     }
  152. }
  153.  
  154. static inline struct free_block *
  155. unlink_block (u_int free_pool, u_char ind, void *block)
  156. {
  157.   struct free_block *fb = (struct free_block *) block;
  158.   struct free_list *fl = free_list + free_pool;
  159.  
  160.   if (! fb)
  161.     {
  162.       fb = (struct free_block *) RemHead ((struct List *) &fl->buckets[ind]);
  163.       if (fb)
  164.     {
  165.       fb = (struct free_block *) ((int)fb - offsetof (struct free_block, next));
  166.       fb->pool = free_pool + 1;
  167.       P(("    unlink_block (%s, %ld) == $%lx\n", 
  168.          free_pool == PRIVATE_POOL ? "PRIVATE" : (free_pool == PUBLIC_POOL ? "PUBLIC" : "BOGOUS"), ind, fb));
  169.  
  170.     }
  171.     }
  172.   else
  173.     {
  174.       P(("    unlink_block (%s, %ld, $%lx)\n", 
  175.      free_pool == PRIVATE_POOL ? "PRIVATE" : (free_pool == PUBLIC_POOL ? "PUBLIC" : "BOGOUS"), ind, fb));
  176.  
  177.       fb->pool = free_pool + 1;
  178.       Remove ((struct Node *) &fb->next);
  179.     }
  180.  
  181.   return fb;
  182. }
  183.  
  184. static void inline
  185. link_block (u_int free_pool, u_char ind, void *block)
  186. {
  187.   struct free_block *fb = (struct free_block *) block;
  188.   struct free_list *fl = free_list + free_pool;
  189.  
  190.   P(("    link_block (%s, %ld, $%lx)\n", 
  191.      free_pool == PRIVATE_POOL ? "PRIVATE" : (free_pool == PUBLIC_POOL ? "PUBLIC" : "BOGOUS"), ind, fb));
  192.  
  193.   fb->pool = 0;    /* we're on the freelist of this pool */
  194.   fb->index = ind; /* and of this size */
  195.   AddHead ((struct List *) &fl->buckets[ind], (struct Node *) &fb->next);
  196. }
  197.  
  198. /* this is a very special log2() function that knows the upper bound
  199.    of its argument, and also automatically rounds to the next upper
  200.    power of two */
  201.  
  202. static inline int const
  203. log2 (int size)
  204. {
  205.   int pow = MAXLOG2;
  206.   int lower_bound = 1 << (MAXLOG2 - 1);
  207.  
  208.   for (;;)
  209.     {
  210.       if (size > lower_bound)
  211.         return pow;
  212.  
  213.       lower_bound >>= 1;
  214.       pow--;
  215.     }
  216. }
  217.  
  218.  
  219. static inline struct free_block *
  220. get_block (u_int free_pool, u_char index)
  221. {
  222.   struct free_block *fb, *buddy;
  223.   struct free_list *fl = free_list + free_pool;
  224.  
  225.   P(("  get_block (%s, %ld)\n", 
  226.      free_pool == PRIVATE_POOL ? "PRIVATE" : (free_pool == PUBLIC_POOL ? "PUBLIC" : "BOGOUS"), index, fb));
  227.  
  228.   if (index == (MAXLOG2 - MINLOG2))
  229.     {
  230.       fb = (struct free_block *) AllocMem (MAXSIZE, fl->exec_attr);
  231.       if (! fb)
  232.         return 0;
  233.  
  234.       fb->exec_block = (int)fb >> 2; /* buddies are relative to this base address */
  235.       fb->pool = free_pool + 1; /* not free */
  236.  
  237.       return fb;
  238.     }
  239.   else 
  240.     {
  241. if (fb = unlink_block (free_pool, index, 0))
  242.     return fb;
  243.     }
  244.  
  245.  
  246.   fb = get_block (free_pool, index + 1);
  247.  
  248.   if (fb)
  249.     {
  250.       /* when splitting a block, we always free the upper buddy. So
  251.          we can just add the size, instead of or'ing the offset to the
  252.          Exec memory block */
  253.       buddy = (struct free_block *)((int)fb + (1 << (index + MINLOG2)));
  254.  
  255.       buddy->exec_block = fb->exec_block;
  256.  
  257.       link_block (free_pool, index, buddy);
  258.     }
  259.  
  260.   return fb;
  261. }
  262.  
  263.  
  264. static inline void
  265. free_block (u_int free_pool, u_char index, struct free_block *fb)
  266. {
  267.   struct free_block *buddy;
  268.  
  269.   buddy = (struct free_block *)
  270.       ((((int)fb - (fb->exec_block<<2)) ^ (1 << (index + MINLOG2)))
  271.        + (fb->exec_block<<2));
  272.  
  273.   if (index == (MAXLOG2 - MINLOG2))
  274.     {
  275.  
  276.       FreeMem (fb, MAXSIZE);
  277.       return;
  278.     }
  279.   else if (buddy->pool || buddy->index != index)
  280.     {
  281.       /* too bad, buddy is not on freelist or of wrong size */
  282.       link_block (free_pool, index, fb);
  283.       return;
  284.     }
  285.  
  286.   /* reserve the buddy, then recombine both */
  287.   unlink_block (free_pool, index, buddy);
  288.  
  289.   /* since the buddy is free as well, recombine both blocks
  290.      and free the twice as large block */
  291.   free_block (free_pool, index + 1, fb < buddy ? fb : buddy);
  292. }
  293.  
  294.  
  295. void *
  296. b_alloc (int size, unsigned pool)
  297. {
  298.   u_char bucket;
  299.   struct free_block *block;
  300.   struct free_list *fl = free_list + pool;
  301.  
  302.   if (size < MINSIZE)
  303.     size = MINSIZE;
  304.  
  305.   /* the additional bytes are needed for the freelist pointer at
  306.      the beginning of each block in use and the base block originally
  307.      obtained from Exec. */
  308.  
  309.   if (size >= BUDDY_LIMIT - offsetof (struct free_block, next))
  310.     return AllocMem (size, pool == PUBLIC_POOL ? MEMF_PUBLIC : 0);
  311.  
  312.   size += offsetof (struct free_block, next);
  313.  
  314.   bucket = log2 (size) - MINLOG2;
  315.  
  316.   /* have to differentiate between PUBLIC and PRIVATE memory here, sigh. 
  317.      PRIVATE memory can safely be accessed by using a semaphore, PUBLIC
  318.      memory however is allocated and free'd inside Forbid(), and using a
  319.      semaphore there would possibly break a Forbid..
  320.      Note: this is safe for use in GigaMem, as GigaMem only uses non-PUBLIC
  321.        memory, if you don't fiddle with attribute masks.. */
  322.   if (pool == PRIVATE_POOL)
  323.     ObtainSemaphore (&fl->sem);
  324.   else
  325.     Forbid();
  326.   block = get_block (pool, bucket);
  327.   if (pool == PRIVATE_POOL)
  328.     ReleaseSemaphore (&fl->sem);
  329.   else
  330.     Permit();
  331.  
  332.   if (block)
  333.     return (void *) & block->next;
  334.   else
  335.     return block;
  336. }
  337.  
  338.  
  339. void
  340. b_free (struct free_block *fb, int size)
  341. {
  342.   u_char bucket;
  343.   struct free_list *fl;
  344.   int free_pool;
  345.  
  346.   if (size < MINSIZE)
  347.     size = MINSIZE;
  348.     
  349.   if (size >= BUDDY_LIMIT - offsetof (struct free_block, next))
  350.     {
  351.       FreeMem ((void *) fb, size);
  352.       return;
  353.     }
  354.  
  355.   size += offsetof (struct free_block, next);
  356.  
  357.   bucket = log2 (size) - MINLOG2;
  358.   fb = (struct free_block *) ((int)fb - offsetof (struct free_block, next));
  359.   free_pool = fb->pool - 1;
  360.   fl = free_list + free_pool;
  361.  
  362.   if (free_pool == PRIVATE_POOL)
  363.     ObtainSemaphore (&fl->sem);
  364.   else
  365.     Forbid();
  366.   free_block (free_pool, bucket, fb);
  367.   if (free_pool == PRIVATE_POOL)
  368.     ReleaseSemaphore (&fl->sem);
  369.   else
  370.     Permit();
  371. }
  372.  
  373.